Many modern operating systems support the use of multithreaded programs, which consist of one or more threads of control that share a common address space and program resources. In multithreaded programs a shared addressable resource, such as a global variable, can be accessed by multiple threads. As a result, the threads of a multithreaded program should be synchronized in order to permit the threads to read from or write to the shared addressable resources without causing a data race. A data race occurs when two or more threads concurrently access a shared variable (memory location) without synchronization and at least one of these accesses is for storing to the shard variable. When a data race condition exists, the value of the shared variable at a particular time in the execution of a thread depends on the order in which the threads accessing the shared variable are executed. Detecting data race conditions is difficult because they are non-deterministic and they may occur as a result of unrelated sections of code accessing the shared variable.
Race conditions may be avoided by incorporating various mechanisms for ensuring that each thread has mutually exclusive access to a shared resource. In one approach, a shared resource is protected by requiring threads to obtain a designated mutually exclusive lock before the shared resource can be modified. Threads without the lock must wait until the current thread releases the lock. Race-free program code may be guaranteed by diligent use of such mutual exclusion locking mechanisms since at each instance only one thread can hold the lock for a particular shared variable.
Various program analysis tools (e.g., debuggers) have been proposed for detecting race conditions. Some program analysis tools are configured to detect data races dynamically during execution of the program code. Dynamic data race detection tools use tracing mechanisms to determine whether a data race occurred during a particular execution of a program. In general, dynamic data race detection methods impose a high overhead on program execution. Other program analysis tools are configured to detect data race conditions statically by, for example, tracing the execution of every path through the program code. Static race detection tools perform a compile-time analysis of a program's source code. In general, static race detection methods tend to generate a significant number of false alarms, making the detection of actual race conditions difficult for programmers.
To summarize, prior approaches for detecting data races impose large performance penalties or are prone to produce erroneous results. What is needed are systems and methods for detecting data race conditions in multithreaded programs in ways that do not impose substantial processing overhead and are significantly less prone to error.